class Solution:
    def longestIncreasingPath(self, matrix: list) -> int:
        def func(matrix, i, j, memo):
            if (i, j) in memo:
                return memo[(i, j)]
            up = 0
            down = 0
            left = 0
            right = 0
            val = matrix[i][j]
            if i - 1 >= 0 and val < matrix[i - 1][j]:
                up = func(matrix, i - 1, j, memo)
            if i + 1 < len(matrix) and val < matrix[i + 1][j]:
                down = func(matrix, i + 1, j, memo)
            if j - 1 >= 0 and val < matrix[i][j - 1]:
                left = func(matrix, i, j - 1, memo)
            if j + 1 < len(matrix[i]) and val < matrix[i][j + 1]:
                right = func(matrix, i, j + 1, memo)

            res = 1 + max(up, down, left, right)

            memo[(i, j)] = res

            return res

        res = 0
        memo = {}
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                res = max(res, func(matrix, i, j, memo))

        return res
